#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

class Solution{
    private:
    int index = -1;
    public:

    int ans1(vector<int>& nums, int target){
        int len = nums.size();
        fun(0, len-1, len, nums, target);

        return index;
    }

    void fun(int left, int right, int len, vector<int>& nums, int target){
        if(left > right){
            return;
        }
        int mid = left + (right - left) / 2;
        if(nums[mid] == target){
            index = mid;
            return;
        }
        fun(left, mid-1, len, nums, target);
        fun(mid+1, right, len, nums, target);
    }
};

void test1(){
    Solution s;
    vector<int> nums = {4,5,6,7,0,1,2};
    int target = 0;

    int ret = s.ans1(nums, target);
    cout << ret << endl;
}

void test2(){
    Solution s;
    vector<int> nums = {4,5,6,7,0,1,2};
    int target = 3;

    int ret = s.ans1(nums, target);
    cout << ret << endl;
}

void test3(){
    Solution s;
    vector<int> nums = {1};
    int target = 0;

    int ret = s.ans1(nums, target);
    cout << ret << endl;
}

int main(void){
    test1();
    test2();
    test3();

    return 0;
}